using BepuUtilities.Collections;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System;

namespace BepuUtilities.Memory
{
    /// <summary>
    /// 表示支持分配和释放的抽象内存块。
    /// 从不移动任何内存。
    /// </summary>
    /// <remarks>Uses an extremely simple ring buffer that makes no attempt to skip groups of allocations. Not particularly efficient.</remarks>
    public class Allocator : IDisposable
    {
        BufferPool pool;
        long capacity;
        /// <summary>
        /// 获取或设置分配器的容量。
        /// </summary>
        public long Capacity
        {
            get { return capacity; }
            set
            {
                if (value < 0)
                    throw new ArgumentException("Capacity must be positive.");
                if (value < capacity)
                {
                    for (int i = 0; i < allocations.Count; ++i)
                    {
                        if (value < allocations.Values[i].End)
                            throw new ArgumentException("Can't reduce capacity below any existing allocation endpoint.");
                    }
                }
                capacity = value;
            }
        }
        /// <summary>
        /// 在下一次分配尝试期间应开始的分配中的索引。
        /// </summary>
        int searchStartIndex;

        public struct Allocation
        {
            public long Start, End;
            public ulong Previous;
            public ulong Next;
        }

        private QuickDictionary<ulong, Allocation, PrimitiveComparer<ulong>> allocations;

        /// <summary>
        /// 创建新的分配器。
        /// </summary>
        /// <param name="Capacity">元素中分配器处理的内存大小。</param>
        /// <param name="initialAllocationCapacity">在内部结构中为其分配空间的估计分配数。</param>
        /// <param name="pool">要从中提取内部资源的池。</param>
        public Allocator(long capacity, BufferPool pool, int initialAllocationCapacity = 128)
        {
            this.pool = pool;
            this.Capacity = capacity;
            allocations = new QuickDictionary<ulong, Allocation, PrimitiveComparer<ulong>>(initialAllocationCapacity, 2, pool);
        }

        /// <summary>
        /// 检查ID当前是否已分配。
        /// </summary>
        /// <param name="id">要检查的ID。</param>
        /// <return>如果ID存在于分配集中,则为True,否则为False。</return>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool Contains(ulong id)
        {
            return allocations.ContainsKey(id);
        }

        /// <summary>
        /// 获取与给定分配ID关联的分配区域(如果存在)。
        /// </summary>
        /// <param name="allocationId">要查找分配的分配ID。</param>
        /// <param name="allocation">与ID关联的分配(如果存在)。</param>
        /// <return>如果allocationId存在于分配器中,则为True,否则为False。</return>
        public bool TryGetAllocationRegion(ulong allocationId, out Allocation allocation)
        {
            return allocations.TryGetValue(allocationId, out allocation);
        }

        /// <summary>
        /// 检查挡路内存是否适合分配器的当前状态。
        /// </summary>
        /// <param name="size">要测试的内存大小。</param>
        /// <param name="IGNOREDIds">对于测试而言,要视为不存在的分配的ID。</param>
        /// <return>如果大小可以容纳,则为True;如果内存不足或内存太零碎,则为False,无法找到一个点。</return>
        public bool CanFit<TPredicate>(long size, ref TPredicate ignoredIds) where TPredicate : struct, IPredicate<ulong>
        {
            if (allocations.Count == 0)
            {
                return size <= Capacity;
            }
            int allocationIndex = searchStartIndex;
            var initialId = allocations.Keys[allocationIndex];
            while (true)
            {
                var allocation = allocations.Values[allocationIndex];
                int nextAllocationIndex;
                Allocation nextAllocation;

                // 跳过任何被忽略的后续分配。
                ulong nextAllocationId = allocation.Next;
                do
                {
                    nextAllocationIndex = allocations.IndexOf(nextAllocationId);
                    nextAllocation = allocations.Values[nextAllocationIndex];
                    nextAllocationId = nextAllocation.Next;
                } while (ignoredIds.Matches(ref nextAllocationId));

                if (nextAllocation.Start < allocation.End)
                {
                    // 绕来绕去,所以缺口从这里到内存挡路的末尾,从内存挡路的开头到下一次分配。
                    // 但是我们需要连续的空间,所以这两个区域必须单独测试。
                    if (Capacity - allocation.End >= size)
                    {
                        return true;
                    }
                    else
                    {
                        if (nextAllocation.Start >= size)
                        {
                            return true;
                        }
                    }
                }
                else
                {
                    // 下一次分配是按顺序进行的。
                    if (nextAllocation.Start - allocation.End >= size)
                    {
                        return true;
                    }

                }
                // 如果我们到了这里,就找不到空地了。
                // 移到下一个地点。
                allocationIndex = nextAllocationIndex;

                // 我们已经绕来绕去了吗？
                if (allocations.Keys[allocationIndex] == initialId)
                {
                    // 绕来绕去却找不到任何空间。
                    return false;
                }
            }
        }

        struct IgnoreNothing : IPredicate<ulong>
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public bool Matches(ref ulong item)
            {
                return false;
            }
        }
        /// <summary>
        /// 检查挡路内存是否适合分配器的当前状态。
        /// </summary>
        /// <param name="size">要测试的内存大小。</param>
        /// <return>如果大小可以容纳,则为True;如果内存不足或内存太零碎,则为False,无法找到一个点。</return>
        public bool CanFit(long size)
        {
            var predicate = default(IgnoreNothing);
            return CanFit(size, ref predicate);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private void AddAllocation(ulong id, long start, long end,
            ref Allocation allocation, ref Allocation nextAllocation)
        {
            var newAllocation = new Allocation
            {
                Next = allocation.Next,
                Previous = nextAllocation.Previous,
                Start = start,
                End = end
            };
            // 请注意,指针修改在新添加之前进行。
            // 这可避免因调整分配字典中的大小而导致的潜在指针无效。
            allocation.Next = id;
            nextAllocation.Previous = id;
            // 即将添加新分配。这次我们这里有空间,所以下次我们很有可能会有更多的空间。将搜索指向此索引。
            searchStartIndex = allocations.Count;
            allocations.Add(id, newAllocation, pool);
        }
        /// <summary>
        /// 尝试分配一定范围的内存。
        /// </summary>
        /// <param name="id">要分配的内存的唯一ID。</param>
        /// <param name="size">要分配的内存大小。</param>
        /// <param name="outputStart">已分配内存的起始索引(如果成功)。</param>
        /// <return>如果分配成功,则为True;如果内存不足或内存太零碎,则为False,无法找到一个点。</return>
        public bool Allocate(ulong id, long size, out long outputStart)
        {
            Debug.Assert(!allocations.ContainsKey(id), "Id must not already be present.");
            if (allocations.Count == 0)
            {
                // 如果是第一次分配,则下一个和前一个指针应该循环。
                if (size <= Capacity)
                {
                    outputStart = 0;
                    allocations.Add(id, new Allocation { Start = 0, End = size, Next = id, Previous = id }, pool);
                    searchStartIndex = 0;
                    return true;
                }
                outputStart = 0;
                return false;
            }
            Debug.Assert(searchStartIndex >= 0 && searchStartIndex < allocations.Count, "Search start index must be within the allocation set!");
            int allocationIndex = searchStartIndex;
            var initialId = allocations.Keys[allocationIndex];
            while (true)
            {
                var allocation = allocations.Values[allocationIndex];
                int nextAllocationIndex = allocations.IndexOf(allocation.Next);
                var nextAllocation = allocations.Values[nextAllocationIndex];
                if (nextAllocation.Start < allocation.End)
                {
                    // 绕来绕去,所以缺口从这里到内存挡路的末尾,从内存挡路的开头到下一次分配。
                    // 但是我们需要连续的空间,所以这两个区域必须单独测试。
                    if (Capacity - allocation.End >= size)
                    {
                        AddAllocation(id, outputStart = allocation.End, allocation.End + size, ref allocations.Values[allocationIndex], ref allocations.Values[nextAllocationIndex]);
                        return true;
                    }
                    else
                    {
                        if (nextAllocation.Start >= size)
                        {
                            AddAllocation(id, outputStart = 0, size, ref allocations.Values[allocationIndex], ref allocations.Values[nextAllocationIndex]);
                            return true;
                        }
                    }
                }
                else
                {
                    // 下一次分配是按顺序进行的。
                    if (nextAllocation.Start - allocation.End >= size)
                    {
                        AddAllocation(id, outputStart = allocation.End, allocation.End + size, ref allocations.Values[allocationIndex], ref allocations.Values[nextAllocationIndex]);
                        return true;
                    }

                }
                // 如果我们到了这里,就找不到空地了。
                // 移到下一个地点。
                allocationIndex = nextAllocationIndex;

                // 我们已经绕来绕去了吗？
                if (allocations.Keys[allocationIndex] == initialId)
                {
                    // 绕来绕去却找不到任何空间。
                    outputStart = 0;
                    return false;
                }
            }
        }

        /// <summary>
        /// 从池中删除与ID关联的内存。
        /// </summary>
        /// <param name="id">要删除的ID。</param>
        /// <return>找到ID的True,否则为False。</return>
        public bool Deallocate(ulong id)
        {
            Allocation allocation;
            if (allocations.TryGetValue(id, out allocation))
            {
                if (allocation.Previous != id)
                {
                    var previousIndex = allocations.IndexOf(allocation.Previous);
                    Debug.Assert(allocations.Values[previousIndex].Next == id, "Previous and current must agree about their relationship.");
                    // 使上一次分配指向下一次分配,以摆脱当前分配。
                    allocations.Values[previousIndex].Next = allocation.Next;

                    var nextIndex = allocations.IndexOf(allocation.Next);
                    Debug.Assert(allocations.Values[nextIndex].Previous == id, "Next and current must agree about their relationship.");
                    // 使下一个分配点指向上一个分配,以摆脱当前分配。
                    allocations.Values[nextIndex].Previous = allocation.Previous;

                }
                else
                {
                    Debug.Assert(allocation.Next == id, "The next index should be itself too, if previous was itself.");
                    Debug.Assert(allocations.Count == 1, "The only time where the previous allocation is itself should be when there is only a single allocation.");
                    // 如果没有更多的分配,则searchStartIndex无关紧要。它将不会在下一次分配中使用。
                }
                allocations.FastRemove(id);
                // 通过去掉这个id,下一次寻找分配的一个有希望的地方是上一次分配旁边的位置！
                // 注意,我们在这里再次请求前面的索引,因为在调用FastRemove期间,前面的索引可能会更改。
                // 如果没有剩余的元素,索引将是无效的,这很好-如果没有元素,那么下一次分配将不会使用searchStartIndex。
                searchStartIndex = allocations.IndexOf(allocation.Previous);
                Debug.Assert(allocations.Count == 0 || (searchStartIndex >= 0 && searchStartIndex < allocations.Count), "Search start index must be within the allocation set!");
                return true;
            }
            return false;
        }


        /// <summary>
        /// 获取分配器中最大连续区域的大小和总可用空间。
        /// 效率不是很高;根据分配数量以线性时间运行。
        /// </summary>
        /// <param name="LargestContiguous">分配器中最大的连续区域。分配器最多可以容纳此大小的分配。</param>
        /// <param name="totalFreeSpace">分配器中的总可用空间。</param>
        public void GetLargestContiguousSize(out long largestContiguous, out long totalFreeSpace)
        {
            if (allocations.Count == 0)
            {
                totalFreeSpace = Capacity;
                largestContiguous = Capacity;
                return;
            }
            largestContiguous = 0;
            totalFreeSpace = 0;
            for (int i = 0; i < allocations.Count; ++i)
            {
                Allocation nextAllocation;
                allocations.TryGetValue(allocations.Values[i].Next, out nextAllocation);
                var toNext = nextAllocation.Start - allocations.Values[i].End;
                if (toNext < 0)
                {
                    // 下一次分配需要环绕,因此实际的连续区域仅从我们的一端到池的末端,
                    // 然后是从0到下一次分配的第二个区域。
                    var adjacent = Capacity - allocations.Values[i].End;
                    var wrapped = nextAllocation.Start;
                    if (largestContiguous < adjacent)
                        largestContiguous = adjacent;
                    if (largestContiguous < wrapped)
                        largestContiguous = wrapped;
                    totalFreeSpace += adjacent + wrapped;
                }
                else
                {
                    if (largestContiguous < toNext)
                        largestContiguous = toNext;
                    totalFreeSpace += toNext;
                }
            }
        }

        /// <summary>
        /// 查找前面有空空间的第一个分配,并将其向前拉以缩小差距。假定具有执行同步重新分配的能力。
        /// </summary>
        /// <param name="id">要移动的分配的ID(如果有)。</param>
        /// <param name="size">移动分配的大小。</param>
        /// <param name="oldStart">分配的旧起始位置。</param>
        /// <param name="Newstart">分配的新开始位置。</param>
        /// <return>如果执行了压缩,则为True,否则为False。</return>
        public bool IncrementalCompact(out ulong id, out long size, out long oldStart, out long newStart)
        {
            // 查找最接近零索引的分配。通过检查需要环回的前一个分配来标识它。
            // 从列表的开头开始,因为它比追加新分配的列表末尾更有可能在那里。
            for (int i = 0; i < allocations.Count; ++i)
            {
                Allocation previousAllocation;
                allocations.TryGetValue(allocations.Values[i].Previous, out previousAllocation);
                if (previousAllocation.End > allocations.Values[i].Start)
                {
                    // 找到列表的开头了！这个指数是第一个指数。
                    // 现在,向前扫描分配链接,查找第一个缺口。
                    var index = i;
                    var previousEnd = 0L;
                    // 请注意,我们在包装前会停下来。
                    for (int iterationIndex = 0; iterationIndex < allocations.Count; ++iterationIndex)
                    {
                        searchStartIndex = index; // 如果遍历结束,我们希望缓存此索引,以便下一次分配将从连续的挡路末尾开始。
                        Debug.Assert(searchStartIndex >= 0 && searchStartIndex < allocations.Count, "Search start index must be within the allocation set!");
                        if (allocations.Values[index].Start > previousEnd)
                        {
                            // 找到了一个缺口。
                            id = allocations.Keys[index];
                            size = allocations.Values[index].End - allocations.Values[index].Start;
                            oldStart = allocations.Values[index].Start;
                            newStart = previousEnd;
                            // 实实在在地执行这个动作。
                            allocations.Values[index].Start = newStart;
                            allocations.Values[index].End = newStart + size;
                            return true;
                        }
                        // 还没有找到差距。移到下一个。
                        previousEnd = allocations.Values[index].End;
                        index = allocations.IndexOf(allocations.Values[index].Next);
                    }
                    break;
                }
            }
            id = 0;
            size = 0;
            oldStart = 0;
            newStart = 0;
            return false;

            // 注意：稍微花哨一点的分配器可以1)跟踪开始分配,2)合并分配,这样整个过程就会变成O(1)。
            // 如果这个分配器出现瓶颈,需要考虑一下。
        }

        /// <summary>
        /// 尝试将给定分配的大小调整为新大小。如果新大小较小,则起始索引保持不变。
        /// </summary>
        /// <param name="id">要调整大小的分配的ID。</param>
        /// <param name="size">分配的新所需大小。</param>
        /// <param name="oldStart">分配的旧开始位置。</param>
        /// <param name="Newstart">分配的新开始位置。</param>
        /// <return>如果调整大小成功,则为True。如果没有足够的空间进行较大的分配,则为False。</return>
        public bool Resize(ulong id, long size, out long oldStart, out long newStart)
        {
            var allocationIndex = allocations.IndexOf(id);
            Debug.Assert(allocationIndex >= 0, "The allocation must be present inside the allocator to resize it!");
            // 当地人裁判会很友好的。
            var allocation = allocations.Values[allocationIndex];
            oldStart = allocation.Start;
            var currentSize = allocation.End - allocation.Start;
            Debug.Assert(size != currentSize, "Why are you calling resize if the new size is the same as the old one?");

            if (size < currentSize)
            {
                // 我们可以调整大小,而不用担心重新分配。
                // 请注意,我们总是通过将终点移到更接近起点的位置来缩小间隔,即使这样做可能会
                // 增加碎片化。但是,通过仅移动端点,我们不需要移动间隔。
                // 在外部,这意味着避免了资源上传。
                // 从概念上讲,增量压缩算法已经导致了对0的偏向。换句话说,
                // 临时引入碎片并不重要,因为增量压缩算法最终
                // 无论哪种方式都做同样数量的工作。所以我们不妨避免做两步棋。
                allocations.Values[allocationIndex].End = allocation.Start + size;
                newStart = allocation.Start;
                return true;
            }
            // 大小正在增加(除非上面的断言被击中！)
            // 这需要重新分配。
            var success = Deallocate(id);
            Debug.Assert(success, "Sanity check: you just looked this allocation up, yet the deallocation failed. Did you introduce a race condition?");
            if (!Allocate(id, size, out newStart))
            {
                // 找不到适合请求大小的位置。按旧大小分配。
                success = Allocate(id, currentSize, out newStart);
                Debug.Assert(success, "You just deallocated a region of this size, so the allocation must succeed. Did you introduce a race condition?");
                return false;
            }
            return true;
        }

        [Conditional("DEBUG")]
        private void ValidatePointers()
        {
            if (allocations.Count == 0)
                return;
            var initialId = allocations.Keys[0];
            ulong backwardId = initialId;
            ulong forwardId = initialId;
            for (int i = 0; i < allocations.Count; ++i)
            {
                var backwardIndex = allocations.IndexOf(backwardId);
                backwardId = allocations.Values[backwardIndex].Previous;

                var forwardIndex = allocations.IndexOf(forwardId);
                forwardId = allocations.Values[forwardIndex].Next;
            }
            Debug.Assert(initialId == backwardId && initialId == forwardId, "We should be able to walk back to the starting id in exactly allocations.Count steps in either direction.");
        }

        public void Dispose()
        {
            allocations.Dispose(pool);
        }
    }
}
